package mergeTwoLists;

import java.util.List;

public class Solution {
      public class ListNode {
      int val;
      ListNode next;
      ListNode() {}
      ListNode(int val) { this.val = val; }
      ListNode(int val, ListNode next) { this.val = val; this.next = next; }
  }
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
//          ListNode ans = new ListNode();
//          ListNode p = ans;
//          ListNode p1 = list1,p2 = list2;
//          while (p1!=null||p2!=null) {
//              if( p1 == null ) {
//                  p.next = p2;
//                  break;
//              } else if ( p2 == null ) {
//                  p.next = p1;
//                  break;
//              } else if ( p1.val < p2.val ) {
//                  p.next = p1;
//                  p1 = p1.next;
//              } else {
//                  p.next = p2;
//                  p2 = p2.next;
//              }
//              p = p.next;
//          }
//          return ans.next;

        // 递归写法
        return merget(list1,list2);
    }
    private ListNode merget (ListNode list1, ListNode list2) {
          if(list1 == null) return list2;
          if(list2 == null) return list1;
          ListNode ans = new ListNode();
          if(list1.val < list2.val) {
              ans.val = list1.val;
              ans.next = merget(list1.next,list2);
          } else {
              ans.val = list2.val;
              ans.next = merget(list1,list2.next);
          }
          return ans;
    }
}
